Sweep Line Algorithm
sweep-line-merge-intervals
Description
Given an array of intervals where intervals[i] = [start_i, end_i], merge all overlapping intervals and return an array of the non-overlapping intervals that cover all the intervals in the input.
Example:
Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].
Video Explanation
Approach
This approach uses a sweep line algorithm. Here's how it works:
- Transform the intervals into events:
- Each interval generates two events: one at the start and one at the end. A start event increases the "active" interval count, while an end event decreases it.
- Sort all events:
- Sort events primarily by time. If two events have the same time, prioritize end events over start events. This ensures the correct merging of intervals.
- Sweep through the events:
- Track when new intervals start and end based on active intervals, and merge intervals accordingly.
C++ Implementation
#include <vector>
#include <algorithm>
#include <iostream>
class Solution {
public:
std::vector<std::vector<int>> merge(std::vector<std::vector<int>>& intervals) {
// Step 1: Create events (start and end) from each interval
std::vector<std::pair<int, int>> events;
for (const auto& interval : intervals) {
events.push_back({interval[0], 1}); // Start event (+1)
events.push_back({interval[1], -1}); // End event (-1)
}
// Step 2: Sort events. Sort by time, and if equal, end (-1) comes before start (+1)
std::sort(events.begin(), events.end(), [](const std::pair<int, int>& a, const std::pair<int, int>& b) {
if (a.first == b.first) return a.second < b.second;
return a.first < b.first;
});
// Step 3: Sweep through the events and merge intervals
std::vector<std::vector<int>> merged;
int active = 0; // Active intervals count
int start = -1; // Start of the current interval
for (const auto& event : events) {
if (active == 0) {
// No active intervals, so this is the start of a new interval
start = event.first;
}
// Update the active intervals count
active += event.second;
if (active == 0) {
// When active becomes 0, we finished an interval
merged.push_back({start, event.first});
}
}
return merged;
}
};
int main() {
Solution sol;
std::vector<std::vector<int>> intervals = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
std::vector<std::vector<int>> result = sol.merge(intervals);
for (const auto& interval : result) {
std::cout << "[" << interval[0] << "," << interval[1] << "] ";
}
return 0;
}
Time and Space Complexity
- Time Complexity:O(n log n), where n is the number of intervals. Sorting the events takes O(n log n), and the sweeping phase takes O(n).
- Space Complexity: O(n) due to the space used for storing events and the output merged intervals.
Test Your Understanding
Answer these 3 questions to check what you have learned.
What is the main topic of this documentation page?
What should be identified before implementing sweep line algorithm?
How is understanding of sweep line algorithm best checked?
Done with this topic? Mark it as complete to track your progress.
💬 Discuss this page
Have a question or spot something confusing in "Sweep Line Algorithm"? Ask below — it's backed by GitHub Discussions, so maintainers get notified like any other GitHub activity.